package com.zofer.study.other;

/**
 * 跳台阶
 * 题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。
 * 求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
 *
 * 推广到一般情况。则可以把n级台阶时的跳法看成是n的函数，记为f(n)。
 * 当n > 2时，第一次跳一级还是两级，决定了后面剩下的台阶的跳法数目的不同：如果第一次只跳一级，
 * 则后面剩下的n-1级台阶的跳法数目为f(n-1)；如果第一次跳两级，
 * 则后面剩下的n-2级台阶的跳法数目为f(n-2)。因此，当n > 2时，
 * n级台阶的不同跳法的总数f(n) = f(n-1) + f(n-2)。其中f(1) = 1,f(2) = 2。
 * 追本溯源，上述问题的本质就是斐波那契数问题。
 */
public class JumpFloor {

    public int JumpFloor(int target) {
        if(target < 0)
            return -1;
        if(target <= 2)
            return target;
        return JumpFloor(target-1)+JumpFloor(target-2);
    }
}
